8.3 插入排序

插入排序是一种简单且直观的排序算法，它的基本思想是将数组分为已排序和未排序两个部分。

通过逐步将未排序部分的元素插入到已排序部分的正确位置，逐步构建整个有序序列。

看起来与选择排序是差不多的，但是还是有一些差别的。

选择排序是一直从未排序序列中选择最小/最大的元素插入到已排序队列中。

而插入排序则是：每次从未排序的序列中拿到第一个元素，与已排序序列的元素比较，之后找到它自己合适的位置插入进去。

本节代码存放目录为 lesson19

概念与原理

插入排序的原理如下：

• 将第一个元素视为已排序部分，其他元素为未排序部分。

• 从未排序部分的第一个元素开始，将其与已排序部分的元素逐个比较，找到其正确位置并插入。

• 重复步骤 2，直到所有元素都插入到已排序部分。

插入排序的基本特点：

• 时间复杂度为 O(n^2)，适合少量数据的排序。

• 插入排序是稳定的，因为相同元素的相对顺序不会改变。

插入排序的步骤示例

给定如下无序数组，按照从小到大排序：

[5, 3, 8, 4, 2]

通过插入排序的步骤如下：

第一轮：

- 第一个元素 5 作为已排序部分，即：[5]

- 将 3 插入到已排序部分 [5]，结果：[3, 5, 8, 4, 2]

第二轮：

- 将 8 插入到已排序部分 [3, 5]，结果：[3, 5, 8, 4, 2]

第三轮：

- 将 4 插入到已排序部分 [3, 5, 8]，结果：[3, 4, 5, 8, 2]

第四轮：

- 将 2 插入到已排序部分 [3, 4, 5, 8]，结果：[2, 3, 4, 5, 8]

最终，排序结果为 [2, 3, 4, 5, 8]。

插入排序的时间复杂度

插入排序的时间复杂度取决于数组的初始状态：

• 最坏情况：O(n²)，即数组是反序排列的。

• 最好情况：O(n)，即数组已经是有序的。

• 平均情况：O(n²)，即数组是随机排列的。

Go语言的实现

实现代码如下：

func insertionSort(arr []int) {
    // 从第二个元素开始遍历，认为第一个元素是已排序的
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1

        // 在已排序部分中寻找插入位置
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j] // 将比key大的元素右移
            j--
        }
        arr[j+1] = key // 插入key到正确位置

        fmt.Printf("第 %d 轮插入结果: %v\n", i, arr)
    }
}

func main() {
    arr := []int{5, 3, 8, 4, 2}
    insertionSort(arr)
    fmt.Println("最终排序结果: ", arr)
}

执行结果如下所示：

第 1 轮插入结果: [3 5 8 4 2]
第 2 轮插入结果: [3 5 8 4 2]
第 3 轮插入结果: [3 4 5 8 2]
第 4 轮插入结果: [2 3 4 5 8]
最终排序结果:  [2 3 4 5 8]

通过上面的实现，我们可以看到插入排序通过一轮一轮地将元素插入到正确的位置，逐渐将整个数组变得有序。

小结

本节我们讲解了插入排序的基本原理、步骤示例和 Go 语言的实现。

关于本节总结如下：

• 时间复杂度：插入排序的时间复杂度为 O(n²)，最坏情况下会逐步遍历所有元素。

• 稳定性：插入排序是稳定的排序算法。

• 应用场景：插入排序适用于数据量较小或部分已排序的场景，且在数组接近有序时效率较高。